本文属于「离散数学」系列文章之一。这一系列着重于离散数学的学习和应用。由于内容随时可能发生更新变动，欢迎关注和收藏离散数学系列文章汇总目录一文以作备忘。此外，在本系列学习文章中，为了透彻理解数学知识，本人参考了诸多博客、教程、文档、书籍等资料。以下是本文的不完全参考目录，在后续学习中还会逐渐补充：

定义5.1 由两个元素 a a a 和 b b b 组成的具有固定次序的序列称为序偶 ordered pair 或二元组 ordered 2-tuples ，记为 ⟨ a , b ⟩ \lang a, b\rang ⟨a,b⟩ 。对于序偶 ⟨ a , b ⟩ \lang a, b\rang ⟨a,b⟩ ， a a a 称为第1元素， b b b 称为第2元素。

在生活中许多事物是成对出现的，事物出现的不同顺序所表示的意义往往是不同的。有了序偶的概念，我们就可以表达出这样的含义。比如将一趟列车的运行区间用一个序偶的形式表示，如 K126 = 。同样，平面上横坐标为 x x x 、纵坐标为 y y y 的点可以表示为 ⟨ x , y ⟩ \lang x, y\rang ⟨x,y⟩ ， ⟨ 2 , 4 ⟩ \lang 2, 4\rang ⟨2,4⟩ 、 ⟨ 4 , 2 ⟩ \lang 4, 2 \rang ⟨4,2⟩ 就表示了平面上两个不同的点。

定义5.2 两个序偶 ⟨ a , b ⟩ \lang a, b\rang ⟨a,b⟩ 和 ⟨ c , d ⟩ \lang c, d\rang ⟨c,d⟩ 相等，即为 ⟨ a , b ⟩ = ⟨ c , d ⟩ \lang a, b\rang = \lang c, d\rang ⟨a,b⟩=⟨c,d⟩ ，当且仅当 a = c ∧ b = d a = c \land b = d a=c∧b=d 。

定义5.3 设 A A A 和 B B B 是两个集合，称集合 A × B = { ⟨ a , b ⟩   ∣   a ∈ A , b ∈ B } A \times B = \{ \lang a, b\rang\ | \ a \in A, b \in B\} A×B={⟨a,b⟩ ∣ a∈A,b∈B}

为 A A A 和 B B B 的笛卡尔积 Cartesian product 或叉集 product set 。

例如， R × R \R \times \R R×R 表示实平面。任取 ⟨ x , y ⟩ ∈ R × R \lang x, y\rang \in \R \times \R ⟨x,y⟩∈R×R ， ⟨ x , y ⟩ \lang x, y\rang ⟨x,y⟩ 表示实平面中的一个点。

例1 设 A = ⟨ a , b ⟩ A = \lang a, b\rang A=⟨a,b⟩ ， B = ⟨ 0 , 1 , 2 ⟩ B = \lang 0, 1, 2\rang B=⟨0,1,2⟩ ， C = ∅ C= \varnothing C=∅ 。求 A × B A\times B A×B、 A × A A\times A A×A、 B × A B\times A B×A、 A × C A\times C A×C 。 解： A × B = { ⟨ a , 0 ⟩ , ⟨ a , 1 ⟩ , ⟨ a , 2 ⟩ , ⟨ b , 0 ⟩ , ⟨ b , 1 ⟩ , ⟨ b , 2 ⟩ } A × A = { ⟨ a , a ⟩ , ⟨ a , b ⟩ , ⟨ b , a ⟩ , ⟨ b , b ⟩ } B × A = { ⟨ 0 , a ⟩ , ⟨ 0 , b ⟩ , ⟨ 1 , a ⟩ , ⟨ 1 , b ⟩ , ⟨ 2 , a ⟩ , ⟨ 2 , b ⟩ } A × C = ∅ \begin{aligned} &A \times B = \{ \lang a, 0\rang , \lang a, 1\rang, \lang a, 2\rang, \lang b, 0\rang , \lang b, 1\rang, \lang b, 2\rang\} \\ &A\times A = \{\lang a, a\rang , \lang a, b\rang , \lang b, a\rang, \lang b, b\rang \} \\ &B\times A = \{ \lang 0, a\rang, \lang 0, b\rang , \lang 1, a\rang , \lang 1, b\rang , \lang 2, a\rang , \lang 2, b\rang \} \\ &A \times C = \varnothing \end{aligned} ​A×B={⟨a,0⟩,⟨a,1⟩,⟨a,2⟩,⟨b,0⟩,⟨b,1⟩,⟨b,2⟩}A×A={⟨a,a⟩,⟨a,b⟩,⟨b,a⟩,⟨b,b⟩}B×A={⟨0,a⟩,⟨0,b⟩,⟨1,a⟩,⟨1,b⟩,⟨2,a⟩,⟨2,b⟩}A×C=∅​

注意，以上序偶和笛卡尔积的概念，可以推广到任意 n n n 个元素和 n n n 个集合上。

定义5.4 由 n n n 个元素 a 1 , a 2 , … , a n a_1, a_2, \dots, a_n a1​,a2​,…,an​ 组成的、具有固定次序的序列称为 n n n 元组 ordered n-tuples ，记为 ⟨ a 1 , a 2 , … , a n ⟩ \lang a_1, a_2, \dots, a_n\rang ⟨a1​,a2​,…,an​⟩ 。对于 n n n 元组 ⟨ a 1 , a 2 , … , a n ⟩ \lang a_1, a_2, \dots, a_n\rang ⟨a1​,a2​,…,an​⟩ ， a 1 a_1 a1​ 称为第1元素， a 2 a_2 a2​ 称为第2元素，依次类推， a i   ( 1 ≤ i ≤ n ) a_i\ (1\le i\le n) ai​ (1≤i≤n) 是该 n n n 元组的第 i i i 个元素。

n n n 元组可以看成是一个二元组（类似于元组的递归定义），规定 ⟨ a 1 , a 2 , … , a n ⟩ = ⟨ ⟨ a 1 , a 2 , … , a n − 1 ⟩ , a n ⟩ \lang a_1, a_2, \dots, a_n\rang = \lang \lang a_1, a_2, \dots, a_{n - 1}\rang, a_n\rang ⟨a1​,a2​,…,an​⟩=⟨⟨a1​,a2​,…,an−1​⟩,an​⟩ ，其中第一元素是 n − 1 n - 1 n−1 元组。例如 ⟨ x , y , z ⟩ \lang x, y, z\rang ⟨x,y,z⟩ 代表 ⟨ ⟨ x , y ⟩ , z ⟩ \lang \lang x, y\rang, z\rang ⟨⟨x,y⟩,z⟩ 、而不代表 ⟨ x , ⟨ y , z ⟩ ⟩ \lang x, \lang y, z\rang\rang ⟨x,⟨y,z⟩⟩（其实这么定义也可以，Haskell中就是这样做的）。

定义5.5 设 A 1 , A 2 , … , A n A_1, A_2, \dots, A_n A1​,A2​,…,An​ 是 n n n 个集合，称集合 A 1 × A 2 × ⋯ × A n = { ⟨ a 1 , a 2 , … , a n ⟩   ∣   a i ∈ A i , 1 ≤ i ≤ n } A_1 \times A_2\times \dots \times A_n = \{ \lang a_1, a_2, \dots, a_n\rang\ | \ a_i \in A_i, 1\le i\le n \} A1​×A2​×⋯×An​={⟨a1​,a2​,…,an​⟩ ∣ ai​∈Ai​,1≤i≤n}

为 A 1 , A 2 , … , A n A_1, A_2, \dots, A_n A1​,A2​,…,An​ 的笛卡尔积 Cartesian product 。若对一切 i i i， A i = A A_i = A Ai​=A ，则 A × A × ⋯ × A ⏟ n 个 \underbrace{A\times A\times \dots \times A}_{n个} n个 A×A×⋯×A​​ 可简记为 A n A^n An 。

例2 设 A = { a , b } , B = { 0 , 1 , 2 } , C = { α , β } A = \{a, b\}, B = \{0, 1, 2\}, C = \{\alpha, \beta\} A={a,b},B={0,1,2},C={α,β} ，求 A × B × C A\times B\times C A×B×C 。

定理5.1 设 A , B , C A, B, C A,B,C 是任意集合，则有以下性质，即笛卡尔积运算对集合的交、并运算都是可分配的（可左分配、也可右分配）： （1） A × ( B ∪ C ) = ( A × B ) ∪ ( A × C ) A \times (B \cup C) = (A\times B) \cup (A\times C) A×(B∪C)=(A×B)∪(A×C) （2） A × ( B ∩ C ) = ( A × B ) ∩ ( A × C ) A \times (B \cap C) = (A\times B) \cap (A \times C) A×(B∩C)=(A×B)∩(A×C) （3） ( A ∪ B ) × C = ( A × C ) ∪ ( B × C ) (A \cup B) \times C = (A \times C) \cup (B \times C) (A∪B)×C=(A×C)∪(B×C) （4） ( A ∩ B ) × C = ( A × C ) ∩ ( B × C ) (A\cap B) \times C= (A\times C) \cap (B \times C) (A∩B)×C=(A×C)∩(B×C) 证明：要证明集合的相等，可以使用集合相等的定义（外延性公理）及其推论：

（1）分别证明 A × ( B ∪ C ) ⊆ ( A × B ) ∪ ( A × C ) A \times (B\cup C) \subseteq (A\times B) \cup (A\times C) A×(B∪C)⊆(A×B)∪(A×C) 和 ( A × B ) ∪ ( A × C ) ⊆ A × ( B ∪ C ) (A\times B) \cup (A\times C) \subseteq A\times (B\cup C) (A×B)∪(A×C)⊆A×(B∪C) ：

（2）分别证明 A × ( B ∩ C ) ⊆ ( A × B ) ∩ ( A × C ) A \times (B \cap C) \subseteq (A\times B) \cap (A\times C) A×(B∩C)⊆(A×B)∩(A×C) 和 ( A × B ) ∩ ( A × C ) ⊆ A × ( B ∪ C ) (A\times B) \cap (A \times C)\subseteq A \times (B\cup C) (A×B)∩(A×C)⊆A×(B∪C) ：

（3）分别证明 ( A ∪ B ) × C ⊆ ( A × C ) ∪ ( B × C ) (A \cup B) \times C \subseteq (A \times C) \cup (B\times C) (A∪B)×C⊆(A×C)∪(B×C) 和 ( A × C ) ∪ ( B × C ) ⊆ ( A ∪ B ) × C (A \times C) \cup (B \times C) \subseteq (A\cup B) \times C (A×C)∪(B×C)⊆(A∪B)×C ：

（4）分别证明 ( A ∩ B ) × C ⊆ ( A × C ) ∩ ( B × C ) (A\cap B) \times C\subseteq (A\times C) \cap (B\times C) (A∩B)×C⊆(A×C)∩(B×C) 和 ( A × C ) ∩ ( B × C ) ⊆ ( A ∩ B ) × C (A\times C) \cap (B \times C)\subseteq (A\cap B) \times C (A×C)∩(B×C)⊆(A∩B)×C ：

定理5.2 如果 A i   ( i = 1 , 2 , … , n ) A_i\ (i = 1, 2, \dots, n) Ai​ (i=1,2,…,n) 都是有限集合，那么 ∣ A 1 × A 2 × ⋯ × A n ∣ = ∣ A 1 ∣ ∙ ∣ A 2 ∣ ∙ ⋯ ∙ ∣ A n ∣ | A_1\times A_2\times \dots \times A_n| = |A_1| \bullet |A_2| \bullet\dots \bullet|A_n| ∣A1​×A2​×⋯×An​∣=∣A1​∣∙∣A2​∣∙⋯∙∣An​∣

证明：（略）

这一定理就是【离散数学】集合论 第三章 集合与关系(3) 集合计数的加法原理、容斥原理提到的、有限集合计数问题的乘法原理 multiplication principle ，它还可以描述为：如果一项工作需要 t t t 步完成，第一步有 n 1 n_1 n1​ 种不同的选择，第二步有 n 2 n_2 n2​ 种不同的选择，以此类推，第 t t t 步有 n t n_t nt​ 种不同的选择，则完成这项工作不同的选择共有 n 1 × n 2 × ⋯ × n t n_1\times n_2\times \dots \times n_t n1​×n2​×⋯×nt​ 种。

例3 某计算机系统的标识符是由英文字母开始，后跟连字符 − - − 或下划线 _ \_ _ ，最后以数字结尾的 3 3 3 位字符串。在不考虑大小写的情况下，该系统中最多可以定义多少个标识符？ 解：开始的英文字母有 26 26 26 种选择，第二位有 2 2 2 种选择，末位数字共有 10 10 10 种选择。因此该系统中最多可定义 26 × 2 × 10 = 520 26\times 2\times 10 = 520 26×2×10=520 个标识符。

例4 考虑以下一段C语言编写的函数，调用该函数后取得的返回值是多少？